package com.huangyi;

public class Main {
    public static void main(String[] args) {
        //归并排序
        class Solution {
            int[] tmp;
            public int[] sortArray(int[] nums) {
                tmp = new int[nums.length];
                mergeSort(nums, 0, nums.length - 1);
                return nums;
            }
            public void mergeSort(int[] nums, int left, int right) {
                if (left >= right) {
                    return;
                }
                int mid = (right + left) / 2;

                mergeSort(nums, left, mid);
                mergeSort(nums, mid + 1, right);

                int i = 0, cur1 = left, cur2 = mid + 1;
                while (cur1 <= mid && cur2 <= right) {
                    tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
                }
                while (cur1 <= mid)   tmp[i++] = nums[cur1++];
                while (cur2 <= right) tmp[i++] = nums[cur2++];

                for (int j = left; j <= right; j++) {
                    nums[j] = tmp[j - left];
                }
            }
        }

        //交易逆序对的总数
        class Solution2 {
            int dest;          // 不用也保留你的字段名
            int[] tmp;

            public int reversePairs(int[] record) {
                if (record == null || record.length < 2) return 0;
                dest = 0;                                  // 按你的风格保留
                tmp = new int[record.length];
                int result = mergeSort(record, 0, record.length - 1);
                return result;
            }

            public int mergeSort(int[] nums, int left, int right) {
                if (left >= right) return 0;
                int mid = left + (right - left) / 2;

                int ret = 0;
                ret += mergeSort(nums, left, mid);
                ret += mergeSort(nums, mid + 1, right);

                int cur1 = left, cur2 = mid + 1, i = 0;
                while (cur1 <= mid && cur2 <= right) {     // 升序合并
                    if (nums[cur1] <= nums[cur2]) {
                        tmp[i++] = nums[cur1++];
                    } else {
                        // 右更小 → 左侧 [cur1..mid] 都 > nums[cur2]
                        ret += (mid - cur1 + 1);
                        tmp[i++] = nums[cur2++];
                    }
                }
                while (cur1 <= mid)   tmp[i++] = nums[cur1++];
                while (cur2 <= right) tmp[i++] = nums[cur2++];

                for (int j = left; j <= right; j++) {
                    nums[j] = tmp[j - left];
                }
                return ret;
            }
        }
    }
}